昨天我們談到了一些關於虛擬記憶體的演算法，今天將繼續接下去說明

Enhanced Second-Chance Algorithm

• 使用昨天提到的reference bit加上modify bit的配對值作為選擇victim page的依據。
• 而以下有4種可能性(reference,modify)：

1. (0,0)：最近沒有被使用過也沒有被修改過的，而這就是最好的victim page。
2. (0,1)：最近雖然沒有被使用過確有被修改過，而這種的就不太好，如果要替換的話就要在替換前寫出。
3. (1,0)：最近有被使用卻沒被修改過的，這種的話可能很快就會再被使用到。
4. (1,1)：最近有被使用也有被修改過，這種的一樣可能很快就會再被使用到，但如果要替換的話一樣要在替換前寫出。

Counting Algorithm

• 為了保持每個page引用數量的計數器演算法。
• 分成兩種：

1. Lease Frequently Used(LFU)：稱作為「不常被使用的演算法」；其定義就是將最少使用次數且參考次數最少的作為victim page。
2. Most Frquently Used(MFU)：稱作為「最常被使用的演算法」；其定義和LFU有點相像，但卻是將次數最少的page認為是剛被帶入不久、很快就需要用到的類型。

Page-Buffering Algorithm

• 簡單的說就是在一個poor裡面有很多修改跟未修改的pages，而當backing store閒置的時候從修改過的pages中挑選一個出來將其寫進硬碟中，然後再將其bit重置成0。
• 對於減少選擇錯誤的victim page很有用，且在重複使用前被reference也不需要在從硬碟中下載下來。

Application and Page Replacement

• 就是說我們前面所有說明過的演算法，都需要OS去推斷關於未來page的存取該如何做。
• 在memory intensive applications中，會造成double buffering的麻煩現象：

1. OS會以為複製在記憶體中的page是I/O buffer在使用，所以也存取了一份page的相關data。
2. Application則會將page保留在記憶體中以供自己的工作使用。
   ==>因此同一份data重複存取的關係，在page in/out時很麻煩，容易在記憶體中搬移時做了需多虛工，導致整體效率下降。

演算法的介紹就到這裡告一段落，接下來我們來說明在分配跟存取時的相關事情吧!

Allocation of Frames

• 分成兩種：

1. Minimum：每個process最少需求的frame數量。
   ==>舉例來說，在IBM370中一個指令是6bytes，所以佔據了2個page，而"from"、"to"這兩個指令也各佔了2個page，所以我們可以知道說IBM370最少需要6個page才能完成搬移的指令動作。
2. Maximum：每個process最多需要多少的frame數量，而這數量限制會由physical memory的大小來決定，但也分成了兩個主要的scheme：
   1-Fixed Allocation：是一種講求公平分配的方法，但卻不是最好的。所以應該要以各process的大小進行分配，其方法就是Proportional allocation，以下就是這個方法的算式過程：
   
   2-Priority Allocation：使用Proportional allocation，但卻是以優先權為考慮並非是以尺寸大小進行分配。但當process產生了page fault的話，就選擇優先權較低的process中選一個frame做替換；或是從自己中選擇一個frame來做替換。

Global vs. Local Allocation

• Global replacement：Process從系統中所有的frame中選擇一個frame來替換，同時也可以將其他正在使用frame的process中挑選並使用。
• Local replacement：Process從自己的frame中挑選一個來進行替換。

Non-Uniform Memory Access(NUMA)

• 簡單來說就是在系統中，記憶體的存取時間不會平等，而是有著相當大的時間差異，就稱為「不一致的記憶體存取」。
• 和系統中的CPU有關，解決方法就是新增lgroups：

1. 建立架構去追蹤CPU跟記憶體是低延遲的group。
2. 接著使用自己的schedule跟pager。
3. 在lgroup中將process的所有threads跟memory排程跟分配
   ==>有提高快取命中率減少記憶體存取時間的結果。

Trashing

• 當一個process中沒有足夠的frames，則發生page fault的機率就會提高很多。
• 變成page fault會得到一個page，並取代現有的frame，可是卻又很快的需要將被取代的frame給叫回來，所以便導致了以下的情形：

1. CPU的使用率降低。
2. 因為CPU效率降低，所以OS會以為需要增加多重處理的等級。
3. 進而變成加入更多的process到記憶體中，最後就是記憶體空間不足的問題。

• 因此簡單的說trashing就是一個process在swapping in跟out之間在忙碌的轉換著
• 以下為示意圖：
  
• 而要解決trashing的方法就是利用working-set model：
  ==>大約評估各個process在不同的執行時期需要多少的frame，並提供足夠的frame防止問題產生。
  ==>使用定義working-set window的參數△，決定working-set的精確度，而其最重要的性質就是其大小，要計算大小WSSi(working set of process Pi)可以寫成：D = Σ WSSi，D就是對frame的需求；所以如果D > m的話就會產生trashing的現象。
• Page-Fault Frequency：是一種比WSS更直接的方法。
  ==>一開始先建立一個「可接受」的page-fault frequency(PFF) rate，並使用logical replacement策略，然後就是察看最後的rate大小如何：

1. 如果actual rate很低，表示process有太多的frame，需要剃除一些走。
2. 如果actual rate很高，就表示process需要更多的frame，因此分配更多的frame給process使用

• 以下就是Working Set跟Page Fault Rate的示意圖：
  

我們還剩最後一部分的虛擬記憶體說明，就留到明天繼續加油吧!